-- 狄克斯特拉算法
--   计算加权图中的最短路径，使用狄克斯特拉算法
--   计算非加权图中的最短路径，使用广度优先搜索
--   只适用于有向无环图 directed acyclic graph
--   不能用于包含负权边的图，Bllman-Ford 算法可处理包含负权边的图
-- 算法说明
--   1. 找出“最便宜”的节点，即可在最短时间内到达的节点
--   2. 更新该节点的邻居的开销
--   3. 重复这个过程，直到对图中的每个节点都处理过
--   4. 计算最终路径

--[[
        ---> a -----
	    |6	 ^     |1
start ---    |     ---> fin 
        |2   |3    |5
	    ---> b -----
]]
local function _build_weighted_graph()
    local graph = {
        start = {
            a = 6,
            b = 2,
        },
        a = {
            fin = 1,
        },
        b = {
            a = 3,
            fin = 5,
        },
        fin = {},
    }

    -- Debug check
    for _, v in pairs(graph) do
        for n in pairs(v) do
            assert(graph[n])
        end
    end

    return graph
end

local function _find_init(graph, start, dest)
    local costs = {}
    local parents = {}
    local neighbors = graph[start]
    for node, cost in pairs(neighbors) do
        costs[node] = cost
        parents[node] = start
    end

    costs[dest] = math.huge
    parents[dest] = nil
    return costs, parents
end

local function _find_lowest_cost_node(costs, processed)
    local lowest_cost = math.huge
    local lowest_cost_node
    for node, cost in pairs(costs) do
        if cost < lowest_cost and not processed[node] then
            lowest_cost = cost
            lowest_cost_node = node
        end
    end
    return lowest_cost_node
end

local function _find_result(start, dest, costs, parents)
    local path_nodes = {dest}
    local path_costs = {}
    local node = parents[dest]
    while node ~= start do
        local to_cost = costs[path_nodes[1]]
        local cost = costs[node]
        table.insert(path_costs, 1, to_cost-cost)
        table.insert(path_nodes, 1, node)
        node = assert(parents[node], node)
    end
    table.insert(path_costs, 1, costs[path_nodes[1]])
    table.insert(path_nodes, 1, start)
    return path_nodes, path_costs
end

local function _find_lowest_cost_path()
    local graph = _build_weighted_graph()
    local start, dest = "start", "fin"
    local costs, parents = _find_init(graph, start, dest)
    
    local processed = {}
    local node = _find_lowest_cost_node(costs, processed)
    while node do
        local cost = costs[node]
        local neighbors = graph[node]
        for n, n_cost in pairs(neighbors) do
            local val = cost + n_cost
            if val < costs[n] then
                costs[n] = val
                parents[n] = node
            end
        end
        
        processed[node] = true
        node = _find_lowest_cost_node(costs, processed)
    end

    return _find_result(start, dest, costs, parents)
end

local function test()
    local path_nodes, path_costs = _find_lowest_cost_path()
    assert(table.concat(path_nodes, "-") == "start-b-a-fin")
    assert(table.concat(path_costs, "-") == "2-3-1")
end

test()

